package com.leet.code.lcof;

public class Code12 {
    public static void main(String[] args) {
        Code12 code12 = new Code12();
//        code12.board = new char[][]{
//                {'A', 'B', 'C', 'E'},
//                {'S', 'F', 'C', 'S'},
//                {'A', 'D', 'E', 'E'}
//        };
//        System.out.println(code12.exist(code12.board, "ABCCESD"));
        code12.board = new char[][]{{'a', 'a'}};
        System.out.println(code12.exist(code12.board, "aaa"));
    }

    int[] is = null, js = null;
    char[] words = null;
    char[][] board = null;

    public boolean exist(char[][] board, String word) {

        this.words = word.toCharArray();
        is = new int[words.length];
        js = new int[words.length];
        this.board = board;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == words[0]) {
                    if (exist(0, i, j)) {
                        return true;
                    }
                }
            }
        }

        return false;

    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }


    public boolean exist(int k, int i, int j) {
        is[k] = i;
        js[k] = j;
        for (int d = 0; d < k; d++) {
            if (is[d] == i && js[d] == j) {
                return false;
            }
        }
        if (k == words.length - 1) {
            return true;
        }

        k++;


        if ((i + 1) < board.length) {
            if (board[i + 1][j] == words[k]) {
                if (exist(k, i + 1, j)) {
                    return true;
                }
            }
        }

        if ((i - 1) >= 0) {
            if (board[i - 1][j] == words[k]) {
                if (exist(k, i - 1, j)) {
                    return true;
                }
            }
        }

        if ((j + 1) < board[0].length) {
            if (board[i][j + 1] == words[k]) {
                if (exist(k, i, j + 1)) {
                    return true;
                }
            }
        }

        if ((j - 1) >= 0) {
            if (board[i][j - 1] == words[k]) {
                if (exist(k, i, j - 1)) {
                    return true;
                }
            }
        }

        return false;

    }

}
